package chapter03;

import java.util.Arrays;

public class NumDistinct115 {
    /**
     * 记忆化搜索
     * 从s中找子序列组合成t的可能性
     * process(chs,cht,s,t) 字符串chs从下标s开始 字符串cht从下标t开始找chs子序列组合成cht的可能性
     * 递归条件
     *  1).cht已经匹配完，返回一种可能性
     *     t==chs.length
     *      return 1
     *  2).chs已经查找完，返回0中可能性
     *     s==chs.length
     *  3).先看chs[s]和cht[t]能否匹配
     *      res=0
     *      a).chs[s]==cht[t]
     *        匹配后续结果
     *        res+=process(chs,cht,s+1,t+1)
     *      b).chs[s]==cht[t]
     *        chs从下一个字符匹配后续结果
     *         res+=process(chs,cht,s+1,t)
     *     将两种情况返回 return res
     *  搜索过程会出现重复解 增加缓存dp[s][t]:字符串cht从下标t开始找chs子序列组合成cht的可能性
     *  但递归仍通不过最后一个测试点 改为动态规划AC O(N^2)
     */
    public int numDistinct1(String s, String t) {
        if(s.length()<s.length()){
            return 0;
        }
        if(s.equals(t)){
            return  1;
        }
        char[] chs=s.toCharArray();
        char[] cht=t.toCharArray();
        int[][] dp=new int[chs.length+1][cht.length+1];
        return process(chs,cht,0,0,dp);
    }

    public int process(char[] chs,char[] cht,int s,int t,int[][] dp){
        if(dp[s][t]!=0){
            return dp[s][t];
        }
        if(t==cht.length){
            dp[s][t]=1;
            return dp[s][t];
        }
        if(s==chs.length){
            dp[s][t]=0;
            return dp[s][t];
        }
        int res=0;
        if(chs[s]==cht[t]){
            res+=process(chs,cht,s+1,t+1,dp);
        }
        res+=process(chs,cht,s+1,t,dp);
        dp[s][t]=res;
        return dp[s][t];
    }

    //动态规划
    public int numDistinct(String s, String t) {
        if(s.length()<s.length()){
            return 0;
        }
        if(s.equals(t)){
            return  1;
        }
        char[] chs=s.toCharArray();
        char[] cht=t.toCharArray();
        int N=chs.length;
        int M=cht.length;
        int[][] dp=new int[N+1][M+1];
        for(int i=0;i<=N;i++){
            dp[i][M]=1;
        }
        for(int i=N-1;i>=0;i--){
            for(int j=M-1;j>=0;j--){
                if(chs[i]==cht[j]){
                    dp[i][j]+=dp[i+1][j+1];
                }
                dp[i][j]+=dp[i+1][j];
            }
        }
        return dp[0][0];
    }
}
